package com.wunong.smart.algorithm.simple.structure;

/**
 * @author created by zealot.zt
 */
public class NodeUtils {

    /**
     * 反转单链表
     *
     * @param node
     * @param <T>
     * @return
     */
    public static <T> Node<T> reverse(Node<T> node) {
        if (node == null) {
            return null;
        }

        if (node.getNext() == null) {
            return node;
        }

        // 创建空节点
        Node<T> head = new Node<>(null);

        // 指向当前节点
        Node<T> cur = node;

        while (cur != null) {
            // 此处针对当前节点cur使用头插入法插入到head中
            // 保存上一个节点的后继
            Node<T> prev = head.getNext();
            // 保存当前节点的后继
            Node<T> next = cur.getNext();

            // head指向当前节点
            head.setNext(cur);

            // 当前节点指向上一个节点
            cur.setNext(prev);

            // 当前指针指向后继节点
            cur = next;
        }

        return head.getNext();
    }

    private NodeUtils() {
    }

}
